Field of the Invention
The present invention relates to methods and systems for modifying bit streams, specifically to methods and systems for inserting chunks of a bits into a bit stream.
Description of the Related Art
Many applications require random values as part of their internal processing. Some of these applications have simple requirements like a uniform distribution of values, reproducibility from a given seed value, and very long cycles before they repeat. To that end, many papers and books describe good hardware and software functions that provide these classic random value generators. The attributes of classic random value generators remain both useful and problematic. Before addressing any shortcomings of current random value generators, we must first review how these generators work.
There exists a number of properties common to all classic random value generators, whether they be hardware or software based. The cornerstone of classic random value generators is the use of static random functions. Each of these functions processes the current non-zero data value into the next random value in the sequence. The subsequent processing of each new value creates the random sequence. Assuming that a good function is used, the random sequence will pass almost all known statistical tests for randomness.
Numerous random functions have been tested and published. Most of these published functions produce a limited sequence of values before repeating the same sequence of random values. These brief cycle lengths may be too short to be compatible with many applications. In hardware, the random functions are most often described as Linear Feedback Shift Registers (LFSR). Though fewer software functions exist, a number of established functions are available for the designer to use in new applications. Also, most software random functions share the same short cycle attribute.
Whether passing or failing, cycle length proves just as important as statistical testing. Combining multiple published functions in a non-linear manner is the most common way to increase cycle length. The function-based random value generators are correctly called pseudorandom generators and remain easy to “crack” (invert). Cracking a random value generator allows an attacker to anticipate each of the values in the sequence. As a rule of thumb, doubling the classic random function complexity has the effect of squaring the effort required to crack it. As the speed of hardware and therefore computers increases, the battle becomes an arms race between the designer of random value generators and the cracker wishing to break them.
Embracing this rule of thumb, hardware designers adopt evermore complex random value generator functions. The struggle between the designer and cracker persists because the function driven paradigm is inevitably incomplete. The cost to create, test, and deploy new random value generators is thereby open-ended, because each new design is destined to become obsolete. Subsequently, higher recurring chip costs translate directly into product costs. The endpoint along this path is unknown, so a designer cannot anticipate how long their newest function will prove safe from cracking.
The costs of increasing function complexity are manifested in multiple ways. As noted above, the hardware arms race persists as an inevitably incomplete problem. Each new jump in hardware technology requires a new corresponding generator design in order to stay ahead of the crackers. This escalating cost forces many application designers to forgo the hardware-based solution. To cut system cost, many application designers resort to software-based random value generators. Often the process of transitioning to a software solution either slows performance unacceptably or increases CPU costs. While the recurring costs are lower without dedicated silicon, the software implementation taxes overall system performance. As the software complexity increases, performance inversely decreases.
In an effort to resist cracking, many designers resort to secret (non-public) designs. Development in secrecy necessitates limited testing, review, or reuse. Unfortunately, secret development guarantees a limited return on investment because low volume of a given design always carries higher cost per unit. Furthermore, secrecy only sustains the integrity of these designs until someone obtains a hardware or software example.
The final weakness to these classic functions stems from a simple immutable fact: each random function produces its own random sequence. Stated another way, there is a one-to-one correspondence between the random function and the unique sequence of values it produces. That sequence acts like a “melody” with respect to its generating function. A random “melody” is defined as both the values and the order of those values as they are produced. The seed value only defines where the “melody” starts.
All classic random value generators use a scalar value (starting non-zero seed) to index the point at which their unique “melody” begins. Since classic random value generators are static function-based constructs, the seed value must be protected because it acts as the key to define the start of the pseudorandom sequence. In most cases, the size of the seed value is used to indicate the overall cycle length. All hardware and most software based classic random value generators require a non-zero seed value to start generating random values. In almost all cases, a zero value seed will fail to generate any random stream.
In a futile effort to resist cracking, many designers resort to secret (non-public) designs. Development in secrecy necessitates limited testing, review, or reuse. Unfortunately, secret development guarantees a limited return on investment because low volume of a given design always carries higher cost per unit. Furthermore, secrecy only sustains the integrity of these designs until someone obtains a hardware or software example. What is needed is a true random value generator, one that implements a true one way function, resulting in a random stream of values that is non-deterministic and/or a method or system that solves one or more of the problems described herein and/or one or more problems that may come to the attention of one skilled in the art upon becoming familiar with this specification.